home *** CD-ROM | disk | FTP | other *** search
/ Just Call Me Internet / Just Call Me Internet.iso / prog / atari / m2 / cat3src / magic / d / mttrees.d < prev    next >
Text File  |  1997-10-26  |  5KB  |  119 lines
  1. (*----------------------------------------------------------------------*
  2.  *                                                                      *
  3.  *  MAGICTOOLS   Modula's  All purpose  GEM  Interface  Cadre  Toolbox  *
  4.  *               ÿ         ÿ            ÿ    ÿ          ÿ               *
  5.  *----------------------------------------------------------------------*
  6.  * Version 3.30  02.02.1992     (C)90/91/92 by Peter Hellinger Software *
  7.  *----------------------------------------------------------------------*
  8.  *            Dieses Modul ist urheberrechtlich geschtzt.              *
  9.  *                                                                      *
  10.  * Die Ver”ffentlichung des Quelltextes oder Teilen daraus, sowie die   *
  11.  * Verbreitung des bersetzten, nicht gelinkten Codes in schriftlicher, *
  12.  * oder maschinenlesbarer Form, insbesondere in Zeitschriften, Mail-    *
  13.  * boxen oder anderen Medien bedarf der ausdrcklichen schriftlichen    *
  14.  * Einverst„ndnisserkl„rung des Autors.                                 *
  15.  *                                                                      *
  16.  * Die Verbreitung des Moduls als Teil eines gelinkten Programms ist    *
  17.  * fr Lizenznehmer ausdrcklich erlaubt!  Der Autor beh„lt sich das    *
  18.  * Recht vor, diese Erlaubnis jederzeit und ohne Angaben von Grnden zu *
  19.  * widerrufen.                                                          *
  20.  *----------------------------------------------------------------------*)
  21.  
  22. (*----------------------------------------------------------------------*
  23.  * mtTrees      Implementiert einen bin„ren Baum.                       *
  24.  *                                                                      *
  25.  * Durch die typlose Datenform der zu speichernden Information kann das *
  26.  * Modul sehr flexibel eingesetzt werden.  Maximale Speichergr”že der   *
  27.  * Information ist 32kb.                                                *
  28.  *----------------------------------------------------------------------*)
  29.  
  30. DEFINITION MODULE mtTrees;
  31.  
  32. FROM MagicSys   IMPORT  Nil, Null, Bit0, Bit1, Bit2, Bit3, Bit4, Bit5, Bit6,
  33.                         Bit7, Bit8, Bit9, Bit10, Bit11, Bit12, Bit13, Bit14,
  34.                         Bit15, LOC, Byte, ByteSet, sWORD, sINTEGER, sCARDINAL,
  35.                         sBITSET, lINTEGER, lCARDINAL, lWORD, lBITSET;
  36.  
  37.  
  38.  
  39.  
  40.  
  41. IMPORT SYSTEM;
  42.  
  43. TYPE    NODE;  (* Eintrag in den Baum *)
  44.  
  45. TYPE    TREE;   (* Baumtyp *)
  46.  
  47. TYPE    CompResult =    (smaller, equal, bigger);
  48.         CompProc =      PROCEDURE ( (* left *)  SYSTEM.ADDRESS, 
  49.                                     (* right *) SYSTEM.ADDRESS): CompResult;
  50. (* Eine Prozedur dieses Typs definiert die Ordnung, in der die Liste
  51.  * angelegt wird.
  52.  * Die Prozedur soll "smaller" returnieren, wenn der Eintrag left kleiner
  53.  * bzw. logisch VOR right einzuordnen ist; equal, wenn die Eintr„ge gleich
  54.  * sind; und bigger wenn der Eintrag left gr”žer bzw. logisch NACH right
  55.  * einzuordnen ist. Die Prozedur bekommt immer POINTER bergeben, daher die
  56.  * ADDRESS-Parameter.
  57.  *
  58.  * Beispiel fr eine CompProc:
  59.  *
  60.  * PROCEDURE Compare (left, rigth: ADDRESS): CompResult;
  61.  * VAR l, r: POINTER TO ARRAY [0..10] OF CHAR;
  62.  * BEGIN
  63.  *  l:= left;  r:= right;
  64.  *  IF l^[0] < r^[0] THEN RETURN smaller; END;
  65.  *  IF l^[0] = r^[0] THEN RETURN equal; END;
  66.  *  RETURN bigger;
  67.  * END Compare;
  68.  *
  69.  *)
  70.  
  71. PROCEDURE NewTree (VAR tree: TREE; comp: CompProc): BOOLEAN;
  72. (* Generiert einen neuen Baum *)
  73.  
  74. PROCEDURE DisposeTree (VAR tree: TREE);
  75. (* L”scht einen Baum, wenn der Baum nicht leer ist, wird er vorher gel”scht. *)
  76.  
  77. PROCEDURE TreeEntries (tree: TREE): lCARDINAL;
  78. (* Anzahl der Eintr„ge im Baum *)
  79.  
  80. PROCEDURE NilNode (): NODE;
  81. (* Liefert einen leeren NODE, zum Vergleichen usw. *)
  82.  
  83. PROCEDURE InsertNode (tree: TREE; info: ARRAY OF LOC): BOOLEAN;
  84. (* Legt ein Element im Baum ab, FALSE wenn dabei ein Fehler auftritt.
  85.  * ACHTUNG! Doppelte Eintr„ge werden ignoriert!
  86.  *)
  87.  
  88. PROCEDURE SearchNode (tree: TREE; from: NODE; info: ARRAY OF LOC;
  89.                       key: CompProc): NODE;
  90. (* Sucht im Baum nach dem Element info, liefert einen Zeiger darauf.
  91.  * Mit key wird eine Prozedur bergeben, die die Elemente vergleicht.
  92.  * Tip: Die in info bergebenen Daten mssen ja nicht komplett sein.
  93.  * Es kommt auf die Prozedur key an...
  94.  *)
  95.  
  96. PROCEDURE DeleteNode (tree: TREE; VAR node: NODE);
  97. (* L”scht einen Eintrag aus dem Baum *)
  98.  
  99. PROCEDURE FirstNode (tree: TREE): NODE;
  100. (* Liefert den ersten Eintrag der Baums *)
  101.  
  102. PROCEDURE LastNode (tree: TREE): NODE;
  103. (* Liefert den letzten Eintrag des Baums *)
  104.  
  105. PROCEDURE NextNode (node: NODE): NODE;
  106. (* Liefert den nachfolgenden Eintrag der Baums *)
  107.  
  108. PROCEDURE PrevNode (node: NODE): NODE;
  109. (* Liefert den vorhergehenden Eintrag der Baums *)
  110.  
  111. PROCEDURE GetNode (node: NODE; VAR info: ARRAY OF LOC): BOOLEAN;
  112. (* šbertr„gt ein Element aus dem Baum. Es wird nur kopiert, wenn die
  113.  * Datenstruktur gleich oder gr”žer als die gespeicherte Struktur ist.
  114.  * FALSE wenn dabei ein Fehler auftritt (info zu klein, node NIL).
  115.  *)
  116.  
  117. END mtTrees.
  118.                                
  119.